#include <iostream>
#include <map>
#include <set>
#include <climits>
#include <vector>
#include <stdio.h>

#include "ej3.h"

using namespace std;
int limitePeligro, n = 0;
set<int> cargasDisponibles;
Resultado resultado(0);
vector< vector<int> > matris;

Resultado::Resultado(int _cantCamiones): cantCamiones(_cantCamiones){}

void recibir_entradas(){
int pel;
cin >> n;
cin >> limitePeligro;
//cout << "recibio n y m" << endl;
//inicializo matriz con ceros y llenando cargas disponibles
matris.resize(n);

for (int i=0; i<(n); i++){
cargasDisponibles.insert(i);
matris[i].resize(n);
	for (int j=0; j<n; j++){
	matris[i][j]=0;
	}
}

//lleno matris con las peligrosidades
for (int i=0; i<(n-1); i++){
	cout << "esperando recibir la fila \"" << i << "\" introduzca "<< (n-1)-i<< " numeros enteros positivos" << endl;
	for(int j=i+1; j<n; j++){
	cin >> pel;
	matris[i][j]= pel;
	matris[j][i]= pel;
	}
	cout << "recibida la fila " << i << endl;
}

}




void printCamion(set<int > d)
{
	for (set<int>::iterator it=d.begin(); it!=d.end(); ++it){
		cout << *it << ", " ;
		}		
}


void printResult(Resultado result){
	cout << "********************************" << endl;
	cout << "Resultado :" << endl;
	
	cout << "CantCamiones: " << result.cantCamiones << " utilizados" << endl;
if (result.cantCamiones > 0){
	for (map< int,CAMION> ::iterator it=(result.camiones).begin(); 
		it!=(result.camiones).end(); 
		it++){	
		cout << "camion " << it->first << ": {" ;
		
		printCamion(it->second.second);
		cout << " }" << endl;
	}
}else{
	cout << "no tiene solucion" << endl;
} 
cout << "***************************" << endl;
}

int sumarCamion(int carga, CAMION &camion,int camionId) //O(cantidad de elementos en el camión (conjunto))
{
	int total = camion.first;
	for (set<int>::iterator inIt=camion.second.begin(); inIt!=camion.second.end();++inIt){ 
		total += matris[carga][*inIt];
		//if (carga < *inIt)
		//{			
			//total += matris[carga][*inIt-carga-1];
		//}
		//if (carga > *inIt)			
		//{
			//total += matris[*inIt][carga-*inIt-1];
		//}
		
	}		

	return total;
}

void buscarCamion(Resultado &resultadoParcial,int carga,int limiteCamiones,int limitePeligro){
	
	int encontro = -1;  //para guardar el id del camion donde ubicar la carga
	
	int totParcial = 0;
	
	//nos fijamos en todos los camiones donde entra el elemento
	for (map< int,CAMION > ::iterator it=(resultadoParcial.camiones).begin(); 		//O(# productos ubicados hasta el momento)
		it!=(resultadoParcial.camiones).end(); 
		it++){					
		totParcial = sumarCamion(carga ,it->second, it->first);			//O(#elem en camion)
		if (  totParcial <= limitePeligro ) {
			encontro = it->first;
			it->second.second.insert(carga);	//O(log #elem en camion)
			it->second.first = totParcial;	
			return;
			break;

		}
		
		totParcial = 0;

	}

	//si no encontro un camion para el prod, lo lleno en uno nuevo
	if (resultadoParcial.cantCamiones < limiteCamiones ){
		resultadoParcial.cantCamiones ++;	
		CAMION nuevoCamion(0,{});
		nuevoCamion.second.insert(carga);
		(resultadoParcial.camiones).insert( std::pair< int,CAMION > (resultadoParcial.cantCamiones,nuevoCamion) );
		//(resultadoParcial.camiones[nuevoIdCamion]).second.insert(carga);
		return;
	}
	resultadoParcial.cantCamiones--;
	return;
}


Resultado ubicarCargas(set<int > cargasDisponibles,int limiteCamiones,int limitePeligro){
	//minima cantidad de camiones usada.
	int camionesMinimo = INT_MAX;
	set<int > disponibles;

	Resultado  resultRecursivo(0), result(0), mejorResult(-1); 
	
    for (set<int>::iterator it=cargasDisponibles.begin(); it!=cargasDisponibles.end(); ++it){
		
    	//extraigo la carga *it;
    	//para las cargas restantes copio y llamo recursivamente
    	disponibles = cargasDisponibles;
    	disponibles.erase(*it);
    	if (disponibles.size()>0){
    		resultRecursivo = ubicarCargas(disponibles,camionesMinimo,limitePeligro);	
    	}

    	if ( resultRecursivo.cantCamiones >= 0 ){
			
    		buscarCamion(resultRecursivo,*it,limiteCamiones,limitePeligro);
    		if ( resultRecursivo.cantCamiones>0 && ( mejorResult.cantCamiones == -1 || resultRecursivo.cantCamiones < mejorResult.cantCamiones) ){
	    		mejorResult = resultRecursivo;    		
    		}
    	}
    }
    
    return mejorResult;
}

int main()
{
  while(cin.peek() != 48) {
	  //cout << "a punto de recibir entradas" << endl;
    recibir_entradas();
    resultado = ubicarCargas(cargasDisponibles,INT_MAX,limitePeligro);
    printResult(resultado);
    cout << "termino primera instancia y a la espera de otra, si terminó, introduza el 0" << endl;
    cin.get();
  }
  
  return 0;
}


